Алгоритм Кнута — Морриса — Пратта

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке, используя то, что при возникновении несоответствия само слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, минуя лишние проверки. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.

Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они опубликовали совместно в 1977 году.

Независимо, в 1969 году, Матиясевич обнаружил аналогичный алгоритм, закодированный двумерной машиной Тьюринга, при изучении задачи распознавания соответствия строк образцу в двоичном алфавите.

Постановка задачи

Даны образец (строка) $\displaystyle S$ и строка $\displaystyle T$. Требуется определить индекс, начиная с которого образец $\displaystyle S$ содержится в строке $\displaystyle T$. Если $\displaystyle S$ не содержится в $\displaystyle T$ — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

Идея

Алгоритм Ахо — Корасик также позволяет искать одну строку за линейное время. Но слабое место этого алгоритма — конечный автомат, который в явном виде строится за O(|needle|·|Σ|) операций и требует столько же памяти.

Если искать всего одну строку, каждое состояние будет иметь только один «прямой» переход. Побочные же переходы будем вычислять динамически, никак их не кэшируя.

если haystack[i] = needle[state]
  то state = state + 1
  иначе state = побочный_переход(state, haystack[i])

Легко заметить, что суффиксные ссылки алгоритма Ахо — Корасик представляют собой префикс-функцию искомого шаблона.

Описание алгоритма и оценка времени работы

Рассмотрим сравнение строк на позиции $\displaystyle i$, где образец $\displaystyle S[0,m-1]$ сопоставляется с частью текста $\displaystyle \displaystyle T[i,i+m-1]$. Предположим, что первое несовпадение произошло между $\displaystyle \displaystyle T[i+j]$ и $\displaystyle S[j]$, где $\displaystyle 1<j<m$. Тогда $\displaystyle T[i,i+j-1]=S[0,j-1]=P$ и $\displaystyle a=T[i+j]\neq S[j]=b$.

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца $\displaystyle S$ сойдется с каким-нибудь суффиксом (конечные символы) текста $\displaystyle P$. Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть значение префикс-функции от строки $\displaystyle S$ для индекса $\displaystyle j$.

Это приводит нас к следующему алгоритму: пусть $\displaystyle {\rm {{\pi }[j]}}$ — значение префикс-функции от строки $\displaystyle S[0,m-1]$ для индекса $\displaystyle j$. Тогда после сдвига мы можем возобновить сравнения с места $\displaystyle T[i+j]$ и $\displaystyle S[{\rm {{\pi }[j]]}}$ без потери возможного местонахождения образца. Можно показать, что таблица $\displaystyle {\rm {\pi }}$ может быть вычислена (амортизационно) за $\displaystyle \Theta (m)$ сравнений перед началом поиска. А поскольку строка $\displaystyle T$ будет пройдена ровно один раз, суммарное время работы алгоритма будет равно $\displaystyle \Theta (m+n)$, где $n$ — длина текста $\displaystyle T$.

Псевдокод для алгоритма

function KMP(S, T) 
  k ← 0
  A ← ø   // A - пустое множество
  π ← Prefix_Function(S)    // считается префикс-функция от образца S
  for i = 1 to |T| do    // |T| - длина строки T
    while k > 0 and T[i] ≠ S[k + 1] do
      k ←  π[k]
    end while
    if T[i] = S[k + 1] then
      k ← k + 1
    end if
    if k = |S| then
      A ← A ⋃ {i - |S| + 1} // это если мы в начале считали префикс-функцию
      A ← A ⋃ {i}           // это если мы в начале считали z-функцию
      k ← π[k]
    end if
  end for
  return A  
end function

Функция возвращает $\displaystyle A$ — множество номеров элементов строки $\displaystyle T$, которыми оканчиваются найденные вхождения $\displaystyle S$ в $\displaystyle T$.

См. также

• Z-функция
• Алгоритм Бойера — Мура

Ссылки

• Алгоритм Кнута-Морриса-Пратта на сайте Algolist, перевод работы Thierry Lecroq, Christian Charras, Knuth-Morris-Pratt algorithm // Цикл лекций Exact String Matching Algorithms, Université de Rouen, 1997